package com.earthchen;

/**
 * 快速排序
 *
 * @author earthchen
 * @date 2018/8/10
 **/
public class QuickSort {

    /**
     * 选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
     * <p>
     * 递归的将p左边和右边的数都按照第一步进行，直到不能递
     *
     * @param a
     * @param start
     * @param end
     */
    public static void sort(int[] a, int start, int end) {
        if (start < end) {
            //选基准值
            int baseNum = a[start];
            //记录中间值
            int midNum;
            int i = start;
            int j = end;
            do {
                while ((a[i] < baseNum) && i < end) {
                    i++;
                }
                while ((a[j] > baseNum) && j > start) {
                    j--;
                }
                if (i <= j) {
                    midNum = a[i];
                    a[i] = a[j];
                    a[j] = midNum;
                    i++;
                    j--;
                }
            } while (i <= j);
            if (start < j) {
                sort(a, start, j);
            }
            if (end > i) {
                sort(a, i, end);
            }
        }
    }
}
